Алгоритъм на пчелите

Алгоритъмът на пчелите (на английски: bees algorithm, да не се греши с Алгоритъм на изкуствените пчелни семейства) е популационен метаевристичен алгоритъм за търсене, разработен през 2005 г. от Дюк Т. Фам (Duc T. Pham) и неговия екип от Университета в Кардиф.^[1] Алгоритъмът имитира поведението на пчелните колонии при търсене на храна. В основната си версия изпълнява един вид локално търсене (търсене в околност), комбинирано с глобалното търсене, и може да се използва както за комбинаторна оптимизация, така и за непрекъсната оптимизация. Алгоритъмът е от вида „изследване и експлоатация“ (exploration and exploitation). Единственото условие за прилагане на алгоритъма на пчелите е да се определи мярка за топологичното разстояние между решенията. Ефективността и специфичните възможности на алгоритъма на пчелите са доказани в редица проучвания.^[2]^[3]^[4]

Биологична метафора

В търсене на храна една колония от медоносни пчели може да се разпръсне на голямо разстояние (над 14 км)^[5] и да събира нектар или цветен прашец от различни хранителни източници, наричани тук цветни петна (flower patches). Една малка част от колонията постоянно претърсва околността (exploration), търсейки нови хранителни източници (цветни петна). Тези пчели, наречени „пчели-разузнавачи“ (scouts), се движат на случаен принцип в района около кошера, оценявайки доходността (нетния добив на енергия) на срещнатите източници на храна.^[5] Когато пчелите-разузнавачи се връщат в кошера, те депозират събраната храна. Индивидите, които са намерили много доходен източник на храна, отиват в област в кошера наречена „дансинг“, и изпълняват ритуал, известен като пчелен танц.^[6] Чрез пчелния танц пчелата-разузнавач съобщава местонахождението на нейното откритие на свободните „пчели-зяпачи“ (onlookers). Пчелите-зяпачи се присъединяват в процеса на експлоатация на открития хранителен източник (exploitation), което в случая на алгоритъма е използване на намерените добри решения. Тъй като продължителността на танца на пчелата-разузнавач е пропорционална на оценката на качеството на източника, повече пчели (събирачи на храна) стават „заети пчели“ (recruited foragers), за да събират храна от най-високо оценените цветни петна. Дотогава докато тези източници се оценяват от разузнавачите като доходни, богати източници на храна, те ще бъдат предлагани от пчелите-разузнавачи при завръщането им в кошера. Заетите пчели могат също да „танцуват“ и да увеличават вербуването на високо доходните цветни петна. Благодарение на този автокаталитичен процес, колонията на пчелите е в състояние бързо да фокуса усилията за събиране на храна от най-доходоносните цветни петна.^[5]

Алгоритъм

Алгоритъмът на пчелите^[2]^[7] имитира стратегията на намиране на храна на пчелите за търсене на най-доброто решение на дадена оптимизационна задача. Всяко кандидат-решение се приема като източник на храна (цвете), а популацията (колонията) на n агенти (пчели) се използва за търсене в пространството на решенията. Всеки път, когато една пчела посещава цвете (т.е. се разглежда дадено решение), тя оценява неговата доходност, т.е. фитнес функция.

Алгоритъмът на пчелите се състои от процедура за инициализация и главен цикъл на търсене, който се повтаря определен брой пъти, или докато се намери решение с приемлив фитнес. Всеки цикъл на търсене се състои от пет процедури:

вербуване (набиране на персонал) (Recruitment),
локално търсене (Local search),
свиване на околността (Neighbourhood shrinking),
изоставяне на места–източници на храна (Site abandonment), и
глобално търсене (Global search).

Псевдокод на стандартен алгоритъм на пчелите^[2]

   1 for i = 1, …, ns
       scout[i] = Initialise_scout()
       flower_patch[i] = Initialise_flower_patch(scout[i])
   2 do until stopping_condition = TRUE
       Recruitment()
       for i = 1, ..., nb
             flower_patch[i] = Local_search(flower_patch[i])
             flower_patch[i] = Site_abandonment(flower_patch[i])
             flower_patch[i] = Neighbourhood_shrinking(flower_patch[i])
       for i = nb, ..., ns
             flower_patch[i] = Global_search(flower_patch[i])

При инициализацията ns пчели-разузнавачи се разполагат на случаен принцип в пространството на търсене, и оценяват фитнеса на „посетените“ решения (цветята, на които са кацнали). За всяко решение, се определят границите на околността, наречена цветно петно (flower patch).

В процедурата за вербуване, пчелите-разузнавачи, които са посетили nb ≤ ns най-добри решения изпълняват танца на пчелата. Тоест, те наемат заети пчели да претърсят допълнително околностите на най-обещаващите решения. Всяка пчела-разузнавач, която намери най-добрите ne ≤ nb решения (елитни места) набира nre заети пчели, докато всяка от останалите nb – ne пчели-разузнавачи наема nrb ≤ nre заети пчели. Така броят на наетите заети пчели зависи от доходността на източника на храна.

В локалната процедура за търсене, набраните заети пчели са разпръснати на случаен принцип в рамките на цветните петна с решенията, посетени от пчелите-разузнавачи (локална експлоатация). Ако някоя от заетите пчели в цветните петна кацне на решение с по-висок фитнес от решението посетено от пчела-разузнавач, тази заета пчела става новата пчела-разузнавач. Ако нито една от заетите пчели не намери решение с по-висок фитнес, размера на цветното петно се свива (намалява) (процедура за свиване на околността). Обикновено, цветните петна са първоначално дефинирани върху голяма площ и размера им постепенно се свива чрез процедурата за свиване на околността. В резултат на това обхвата на локална експлоатация постепенно се фокусира върху зона непосредствено близка до най-добрия локален максимум. Ако се установи, че за предварително определен брой цикли от търсенето няма подобрение във фитнеса в дадено цветно петно, локалният максимум на фитнес функцията се счита за установен. Това цветно петно се изоставя (процедура изоставяне на места–източници на храна), и на случаен принцип се генерира нова пчела-разузнавач.

Както в биологичните пчелни семейства,^[5] малък брой пчели-разузнавачи поддържат изследването на пространството на решенията (exploration), като търсят нови области с висок фитнес (глобално търсене). Процедурата за глобално търсене повторно инициализира (ре-инициализира) последните ns – nb цветни петна с генерирани на случаен принцип решения.

В края на един цикъл за търсене, популацията (колонията) на пчелите-разузнавачи отново се състои от ns пчели-разузнавачи: nr пчели-разузнавачи, генерирани от локалната процедура за търсене (някои от които може да са били повторно инициализирани от процедурата за изоставяне на места), и ns – nb пчели-разузнавачи, генерирани от глобална процедура за търсене. Общият брой на популацията (колонията) на пчелите е n = ne•nre + (nb – ne)•nrb + ns (заетите пчели от елитните места + заетите пчели от останалите добри места + пчелите-разузнавачи) пчели.

Вижте също

Алгоритъм на изкуствените пчелни семейства

Източници

↑ Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005.
↑ ^а ^б ^в Pham, D.T., Castellani, M. (2009), The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems. Proc. ImechE, Part C, 223(12), 2919 – 2938.
↑ Pham, D.T. and Castellani, M. (2013), Benchmarking and Comparison of Nature-Inspired Population-Based Continuous Optimisation Algorithms, Soft Computing, 1 – 33.
↑ Pham, D.T. and Castellani, M. (2015), A comparative study of the bees algorithm as a tool for function optimisation, Cogent Engineering 2(1), 1091540.
↑ ^а ^б ^в ^г Tereshko V., Loengarov A., (2005) Collective Decision-Making in Honey Bee Foraging Dynamics Архив на оригинала от 2014-02-01 в Wayback Machine.. Journal of Computing and Information Systems, 9(3), 1 – 7.
↑ Von Frisch, K. (1967) The Dance Language and Orientation of Bees. Harvard University Press, Cambridge, MA.
↑ Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M., The Bees Algorithm, A Novel Tool for Complex Optimisation Problems, Proc 2nd Int Virtual Conf on Intelligent Production Machines and Systems (IPROMS 2006), Oxford: Elsevier, pp. 454 – 459, 2006.

Тази страница частично или изцяло представлява превод на страницата Bees algorithm в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.

[Pham_&_al,_2005-1] Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manufacturing Engineering Centre, Cardiff University, UK, 2005.

[Pham_&_Castellani,_2009-2] а ^б ^в Pham, D.T., Castellani, M. (2009), The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems. Proc. ImechE, Part C, 223(12), 2919 – 2938.

[3] Pham, D.T. and Castellani, M. (2013), Benchmarking and Comparison of Nature-Inspired Population-Based Continuous Optimisation Algorithms, Soft Computing, 1 – 33.

[4] Pham, D.T. and Castellani, M. (2015), A comparative study of the bees algorithm as a tool for function optimisation, Cogent Engineering 2(1), 1091540.

[Tereshko_&_Loengarov,_2005-5] а ^б ^в ^г Tereshko V., Loengarov A., (2005) Collective Decision-Making in Honey Bee Foraging Dynamics Архив на оригинала от 2014-02-01 в Wayback Machine.. Journal of Computing and Information Systems, 9(3), 1 – 7.

[6] Von Frisch, K. (1967) The Dance Language and Orientation of Bees. Harvard University Press, Cambridge, MA.

[7] Pham D.T., Ghanbarzadeh A., Koc E., Otri S., Rahim S., Zaidi M., The Bees Algorithm, A Novel Tool for Complex Optimisation Problems, Proc 2nd Int Virtual Conf on Intelligent Production Machines and Systems (IPROMS 2006), Oxford: Elsevier, pp. 454 – 459, 2006.

[1]

[2]

[3]

[4]

[5]

[6]

[7]